package sort;

/**
 * @description: 归并排序(nlgn)
 * @title: MergerSort
 * @author: zp
 * @date: 2021/11/18 20:36
 */
public class MergerSort extends BaseSort {

    public static void main(String[] args) {
        int count = 6;
        Integer[] ints = new Integer[count];
        for (int i = 0; i < count; i++) {
            ints[i] = (int) (Math.random() * count);
        }
        long start = System.currentTimeMillis();
        sort(ints);
        long end = System.currentTimeMillis();
        System.out.println((end - start));
        show(ints);
    }

    public static void sort(Comparable[] a) {
        Comparable[] aux = new Comparable[a.length];
        sort(a, aux, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        //获取每一次的归并点
        int mid = lo + (hi - lo) / 2;
        //按照归并点的地方进行拆分排序
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        //把拆分排序后的数组归并成一个新的大数组 如此递归
        merge(a, aux, lo, mid, hi);
    }

    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
        //拷贝元素打临时数组当中
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }

        // 左边的初始点i 右边的初始点j
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            //如果i大于右边的初始点 说明左边已经排序完成 直接把右边的元素依次放入大数组当中
            if (i > mid) {
                a[k] = aux[j++];
            }
            //如果j大于右边的结束点 说明右边已经排序完成 直接把左边的元素依次放入大数组当中
            else if (j > hi) {
                a[k] = aux[i++];
            }
            //如果遍历的元素右边小于左边 就把右边的的元素放入大数组中
            else if (less(aux[j], aux[i])) {
                a[k] = aux[j++];
            }
            //如果遍历的元素左边小于右边 就把左边的的元素放入大数组中
            else {
                a[k] = aux[i++];
            }
        }

    }
}
